﻿using System;
using System.Collections.Generic;
using System.ComponentModel.Design;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


public class Solution74
{
    public bool SearchMatrix2(int[][] matrix, int target)//顺序查找
    {
        int row = 0;
        while (row < matrix.Length)
        {

            if (matrix[row][0] < target)
            {
                row++;
            }
            else if(matrix[row][0] == target)
            {
                return true;
            }
            else
            {
                row--;
                break;


            }
        }
        if (row < 0||row>= matrix.Length)
        {
            return false;
        }
        for (int i = 0; i < matrix[row].Length; i++)
        {

            if (target == matrix[row][i])
            {

                return true;
            }
        }
        return false;
    }
    public bool SearchMatrix(int[][] matrix, int target)//两次二分查找
    {
        int top = 0;
        int bottom = matrix.Length-1;
        int row = (top+ bottom+1) /2;
      

        while (top < bottom)
        { Console.WriteLine(row);
            if (matrix[row][0] < target)
            {//在下班区间
                top = row;


            }
            else if (matrix[row][0] == target)
            {
                return true;
            }
            else
            {
                bottom = row-1;


            }
            row = (top + bottom+1) / 2;
           
        }


        int left = 0;
        int right = matrix[0].Length - 1;
        int col = (left + right + 1) / 2;

        while (left < right)
        {
            if (matrix[row][col] < target)
            {//在下班区间
                left = col+1;


            }
            else if (matrix[row][col] == target)
            {
                return true;
            }
            else
            {
                right = col-1;


            }
            col = (left + right + 1) / 2;
        }
        return false;
    }
}
class Program74
{

    static void Main74(string[] args)
    {
        Solution74 solution = new Solution74();
        //int[][] matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]];
        int[][] matrix = [[1]];
        bool res =    solution.SearchMatrix(matrix, 1);
        Console.WriteLine(res);
    }


}